import java.util.Random;

public class 分成k份的最大乘积 {
    // 分成k份的最大乘积
    // 一个数字n一定要分成k份，得到的乘积尽量大是多少
    // 数字n和k，可能非常大，到达10^12规模
    // 结果可能更大，所以返回结果对 1000000007 取模
    // 来自真实大厂笔试，没有在线测试，对数器验证
    public static int mod = 1000000007;

    public static int maxValue1(int n, int k) {
        return dfs(n,k);
    }

    private static int dfs(int n, int k) {
        if (k == 1) {
            return n;
        }
        int ans = Integer.MIN_VALUE;
        for (int i = 1; i <= n - k + 1; i++) {
            ans = Math.max(i * dfs(n - i,k - 1),ans);
        }
        return ans;
    }

    public static int maxValue2(int n, int k) {
        int x = n / k;
        int y = n % k;
        return (power(x + 1,y) * power(x,k - y)) % mod;
    }

    private static int power(int x, int n) {
        int ans = 1;
        while (n > 0) {
            if ((n & 1) == 1) {
                ans = (ans * x) % mod;
            }
            n >>= 1;
            x = (x * x) % mod;
        }
        return ans;
    }

    public static void main(String[] args) {
        int N = 30;
        int group = 2000;
        for (int i = 1; i <= group; i++) {
            int n = (int) (Math.random() * N) + 1;
            int k = (int) (Math.random() * n) + 1;
            if (maxValue1(n,k) != maxValue2(n,k)) {
                System.out.println("出错了");
            }
            if (i % 100 == 0) {
                System.out.println("测试到第" + i + "组");
            }
        }
        System.out.println("结束");
    }
}
